#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

string integerToRoman(int input)
{
    string ans;
    map<int, string> myMap;
    myMap[1000] = "M";
    myMap[900] = "CM";
    myMap[500] = "D";
    myMap[400] = "CD";
    myMap[100] = "C";
    myMap[90] = "XC";
    myMap[50] = "L";
    myMap[40] = "XL";
    myMap[10] = "X";
    myMap[9] = "IX";
    myMap[5] = "V";
    myMap[4] = "IV";
    myMap[1] = "I";

    for (map<int, string>::reverse_iterator iter = myMap.rbegin(); iter != myMap.rend(); iter++) {
        if (input == 0) break;
        while (input >= iter->first) {
            //cout << input << " " << iter->first << endl;
            input -= iter->first;
            ans += iter->second;
        }
    }

    return ans;
}

//test in online judge and all pass
int main(int argc, char **argv)
{
    string result;

    cout << "----------Test 1----------" << endl;
    result = integerToRoman(954);
    cout << result << endl;

    cout << "----------Test 2----------" << endl;
    result = integerToRoman(369);
    cout << result << endl;
}
